package linked;

/**
 * Created by lzan13 on 2024/03/14
 * 描述单向链表节点类
 */
public class SingleLinkedList<T> {
    // 链表头节点
    private LinkedNode<T> headNode;
    // 链表尾节点
    private LinkedNode<T> lastNode;
    // 链表大小
    private int count;

    /**
     * 添加新数据
     *
     * @param data 新的数据
     */
    public void add(T data) {
        LinkedNode<T> node = new LinkedNode<T>();
        node.setData(data);
        if (headNode == null) {
            headNode = node;
        } else {
            LinkedNode<T> tempNode = headNode;
            while (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
            }
            tempNode.setNext(node);
        }
        lastNode = node;
        count++;
    }

    /**
     * 插入指定位置
     *
     * @param index 指定位置
     * @param data  数据
     */
    public void add(int index, T data) {
        LinkedNode<T> node = findByIndex(index);

    }

    /**
     * 在指定数据之前插入数据
     *
     * @param data    要插入的指定数据之前的数据
     * @param newData 新数据
     */
    public void addBefore(T data, T newData) {

    }

    /**
     * 移除指定下标数据
     *
     * @param index 移除的数据下标
     */
    public void removeAt(int index) {
        LinkedNode<T> node = findByIndex(index);

        LinkedNode<T> node = new LinkedNode<T>();
        node.setData(data);
        if (headNode == null) {
            headNode = node;
            count++;
            return;
        }
        LinkedNode<T> tempNode = headNode;
        while (tempNode.getNext() != null) {
            tempNode = tempNode.getNext();
        }
        tempNode.setNext(node);
        count++;
    }

    /**
     * 根据下标查找节点
     *
     * @param index
     */
    private LinkedNode<T> findByIndex(int index) {
        checkIndex(index);
        // TODO 优化点：双向链表时可用 index 与链表取半比较，大了从头遍历，小了从尾遍历
        LinkedNode<T> tempNode = headNode;
        int i = 0;
        while (tempNode != null && index != i) {
            tempNode = tempNode.getNext();
            i++;
        }
        return tempNode;
    }

    /**
     * 检查下标是否越界
     *
     * @param index 下标
     */
    private void checkIndex(int index) {
        if (index < 0 || index > count) {
            throw new IndexOutOfBoundsException(String.format("index: %d, count:%d", index, count));
        }
    }
}
